/*
*Copyright (c) 2012, The Linux Foundation. All rights reserved.
*Redistribution and use in source and binary forms, with or without
*modification, are permitted provided that the following conditions are
*met:
    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above
      copyright notice, this list of conditions and the following
      disclaimer in the documentation and/or other materials provided
      with the distribution.
    * Neither the name of The Linux Foundation nor the names of its
      contributors may be used to endorse or promote products derived
      from this software without specific prior written permission.

*THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
*WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
*MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
*ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
*BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
*CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
*SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
*BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
*WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
*OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
*IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
*/

#include "malloc.h"
#include "fstool_common.h"
#include "fsck_fragment.h"

RBT_HEAD(FSCK_FRAGMENT, FSCK_FRAGMENT_S) ;
struct FSCK_FRAGMENT g_stFreeCluster,g_stBadCluster;
struct FSCK_FRAGMENT_S* FSCK_FRAGMENT_RBT_FIND(struct FSCK_FRAGMENT* x, struct FSCK_FRAGMENT_S* y);
struct FSCK_FRAGMENT_S* FSCK_FRAGMENT_RBT_REMOVE(struct FSCK_FRAGMENT* x, struct FSCK_FRAGMENT_S* y);
struct FSCK_FRAGMENT_S* FSCK_FRAGMENT_RBT_NEXT(struct FSCK_FRAGMENT_S* y);
struct FSCK_FRAGMENT_S* FSCK_FRAGMENT_RBT_INSERT(struct FSCK_FRAGMENT* x, struct FSCK_FRAGMENT_S* y);
struct FSCK_FRAGMENT_S* FSCK_FRAGMENT_RBT_MIN(struct FSCK_FRAGMENT* x);

static int FSCK_FRAGMENT_Cmp(struct FSCK_FRAGMENT_S *frag1 ,struct FSCK_FRAGMENT_S *frag2)
{
    if (frag1->head > frag2->head)
    {
        return 1;
    }
    else if (frag1->head < frag2->head)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}
RBT_GENERATE(FSCK_FRAGMENT,FSCK_FRAGMENT_S,rb,FSCK_FRAGMENT_Cmp); /*lint !e19 !e613*/

FSCK_FRAGMENT_S* FSCK_FRAGMENT_New(void)
{
    struct FSCK_FRAGMENT_S *frag = NULL;
    frag = calloc(1,sizeof(struct FSCK_FRAGMENT_S));
    if(!frag)
    {
        FSTOOL_COMM_LOG_WARN("%s,No space left \n",__func__);
        return NULL;
    }
    RBT_SET(frag,NULL,rb);
    return frag;
}

void FSCK_FRAGMENT_Free(void* head)
{
    struct FSCK_FRAGMENT_S *frag = NULL;
    struct FSCK_FRAGMENT_S *next_frag = NULL;

    FSTOOL_COMM_LOG_INFO("FSCK_FRAGMENT_Free\n");
    frag = FSCK_FRAGMENT_RBT_MIN(head);
    if(!frag)
    {
        FSTOOL_COMM_LOG_INFO("%s: rb_tree is empty \n",__func__);
        return ;
    }
    while (frag)
    {
        next_frag = FSCK_FRAGMENT_RBT_NEXT(frag);
        /*before free it ,must remove it from the rb_tree*/
        (void)FSCK_FRAGMENT_RBT_REMOVE(head,frag);
        free(frag);
        frag = next_frag;
    }
}

FSCK_FRAGMENT_S* FSCK_FRAGMENT_Find(void* pstHead, FSCK_FRAGMENT_S* pstNode)
{
    return FSCK_FRAGMENT_RBT_FIND((struct FSCK_FRAGMENT*)pstHead, pstNode);
}

void FSCK_FRAGMENT_Remove(void* pstHead, FSCK_FRAGMENT_S* pstNode)
{
    (void)FSCK_FRAGMENT_RBT_REMOVE((struct FSCK_FRAGMENT*)pstHead, pstNode);
    return;
}

FSCK_FRAGMENT_S* FSCK_FRAGMENT_Insert(void* pstHead, FSCK_FRAGMENT_S* pstNode)
{
    return FSCK_FRAGMENT_RBT_INSERT((struct FSCK_FRAGMENT*)pstHead, pstNode);
}

FSCK_FRAGMENT_S* FSCK_FRAGMENT_Min(void* pstHead)
{
    return FSCK_FRAGMENT_RBT_MIN((struct FSCK_FRAGMENT*)pstHead);
}

FSCK_FRAGMENT_S* FSCK_FRAGMENT_Next(FSCK_FRAGMENT_S* pstNode)
{
    return FSCK_FRAGMENT_RBT_NEXT(pstNode);
}
